package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.ListNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 重排链表
 * https://leetcode.cn/problems/reorder-list/
 *
 * @time 2024/1/18
 */
public class ReorderList {

//    public static void main(String[] args) {
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(2);
//        ListNode l3 = new ListNode(3);
//        ListNode l4 = new ListNode(4);
//        ListNode l5 = new ListNode(5);
//        l1.next = l2;
//        l2.next = l3;
//        l3.next = l4;
//        l4.next = l5;
//
//        ReorderList rl = new ReorderList();
//        rl.reorderList(l1);
//
//    }

    public void reorderList(ListNode head) {
        List<ListNode> list = toList(head);
        int size = list.size();
        List<ListNode> newList = new ArrayList<>();
        for (int i = 0; i < size / 2; i++) {
            newList.add(list.get(i));
            newList.add(list.get(size - 1 - i));
        }
        if (size % 2 == 1) {
            newList.add(list.get(size / 2));
        }
        for (int i = 0; i < size - 1; i++) {
            newList.get(i).next = newList.get(i + 1);
        }
        newList.get(size - 1).next = null;
    }

    private List<ListNode> toList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        ListNode tmp = head;
        while (tmp != null) {
            list.add(tmp);
            tmp = tmp.next;
        }
        return list;
    }
}
